home *** CD-ROM | disk | FTP | other *** search
/ TeX 1995 July / TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO / tex-k / tex-k-archive.past / tex-k-archive.gz / tex-k-archive / 000377_fj@iesd.auc.dk_Sat Mar 12 21:42:55 1994.msg < prev    next >
Internet Message Format  |  1994-10-11  |  2KB
  1. Received: from iesd.auc.dk by cs.umb.edu with SMTP id AA03464
  2.   (5.65c/IDA-1.4.4 for <tex-k@cs.umb.edu>); Sat, 12 Mar 1994 14:43:36 -0500
  3. Received: from loke.iesd.auc.dk (loke.iesd.auc.dk [130.225.48.20]) by iesd.auc.dk (8.6.5/8.6.5) with ESMTP id UAA10630; Sat, 12 Mar 1994 20:43:33 +0100
  4. From: Frank Jensen <fj@iesd.auc.dk>
  5. Received: from localhost (fj@localhost) by loke.iesd.auc.dk (8.6.4/8.6.4) id UAA24887; Sat, 12 Mar 1994 20:42:55 +0100
  6. Date: Sat, 12 Mar 1994 20:42:55 +0100
  7. Message-Id: <199403121942.UAA24887@loke.iesd.auc.dk>
  8. To: tex-k@cs.umb.edu
  9. Subject: Kpathsearch 1.7 -- comments on "hash.c"
  10.  
  11.  
  12. I have two comments.
  13.  
  14. 1) The hash function is not particularly good.  It computes the sum of
  15. all characters in the key, multiplies the result by two, and finally
  16. takes modulo the hash table size.  [The multiplication by two is done
  17. in a strange way.]
  18.  
  19. If we assume that an average key has length between 5 and 10, that the
  20. ASCII character set is being used, and that a typical character is a
  21. lower case letter (so that its numeric value is around 100), then the
  22. hash value of an average key will be between 1000 and 2000 (assuming
  23. the size of the hash table is at least 2000).  The hash table created
  24. by the database search code has size 7603, meaning that we can expect
  25. the last 5000 buckets to be empty (and we can expect a clustering
  26. around bucket 1500).
  27.  
  28. It will be better to choose a hash function that spreads out the keys
  29. in different buckets.
  30.  
  31. Here is one from Knuth's CWEB system (rewritten in Kpathsearch style):
  32.  
  33. static unsigned
  34. hash P2C(hash_table_type, table,  const_string, key)
  35. {
  36.   unsigned n = 0;
  37.  
  38.   while (*key != 0)
  39.     {
  40.       n *= 2; n += (unsigned char) *key++;
  41.     }
  42.  
  43.   return n % table.size;
  44. }
  45.  
  46.  
  47. 2) In `hash_create', the buckets are created using `calloc'.
  48. According to the ANSI standard, `calloc' initializes all bits to zero,
  49. and it is explicitly mentioned that this is not necessarily the
  50. representation of a null pointer (or a floating-point zero).  So I
  51. think it's best to explicitly initialize all buckets with a null
  52. pointer.
  53.  
  54. ---
  55. Frank Jensen,   fj@iesd.auc.dk
  56. Department of Mathematics and Computer Science
  57. Aalborg University
  58. DENMARK